home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / lists / gem / l_1199 / 1149 < prev    next >
Text File  |  1994-08-27  |  10KB  |  458 lines
  1. Subject: ShortCuts - TSR code
  2. Date: Mon, 01 Aug 1994 18:38:38 +1000
  3. From: Warwick Allison <warwick@cs.uq.oz.au>
  4. Precedence: bulk
  5.  
  6.  
  7. I have written the main body of the tree-based storage scheme
  8. for APP_DEFS.SYS.
  9.  
  10. It's very fast, and quite small.  It is included below.
  11.  
  12. I haven't written the actual TSR/cookie stuff, just the actual storage
  13. and retrieval mechanism (ie. the hard part).  This code could even be used
  14. outside a TSR - in the app itself, and it would be the fastest way to
  15. retrieve attributes.  (In that case, I would add an extra line to filter
  16. out the settings of attributes for applications other than the loader).
  17.  
  18. I hope this demonstrates the utility of the app_defs.sys format which I have
  19. proposed.  It contains sample look-up code, which gives the following
  20. result:
  21.  
  22. Given an app_defs.sys file (note, no " " near ":"):
  23.  
  24. *.quit.key:^Q
  25. *.quit.name:Quit
  26. *.new.key:^N
  27. *.new.name:New
  28. *.open.key:^O
  29. *.open.name:Open...
  30. *.close.key:^C
  31. *.close.name:Close
  32. *.selectall.key:^A
  33. atariworks.*selectall.key:+^A
  34. gumby.*.selectall.key:+^B
  35. *.confirmexit.flag: no
  36. calamus.confirmexit.flag: yes
  37.  
  38. It match the following attribute/values:
  39.  
  40. mydraw.quit.key:^Q
  41. atariworks.quit.name:Quit
  42. atariworks.selectall.key:+^A
  43. atariworks.wp.selectall.key:+^A
  44. atariworks.db.selectall.key:+^A
  45. atariworks.ss.selectall.key:+^A
  46. gumby.foo.selectall.key:+^B
  47. gumby.selectall.key:^A
  48.  
  49.  
  50. /* APP_DEFS.SYS TSR
  51. **
  52. ** Author:  Warwick Allison (warwick@cs.uq.oz.au)
  53. **          (Copyright)
  54. **
  55. ** Reads APP_DEFS.SYS file, installs a cookie providing access to the
  56. ** defaults via a simple interface.
  57. **
  58. ** Defaults are stored in a highly efficient tree, allowing attribute
  59. ** look-up in O(length-of-attribute) time, regardless of number of
  60. ** defaults actually stored.  Storage cost of the tree may be LESS THAN
  61. ** the total size of the app_defs file (since common prefixes are shared).
  62. **
  63. ** eg.
  64. **     a.b.c:1
  65. **     a.b.d:2
  66. **
  67. ** is stored as:
  68. **
  69. **     a.b
  70. **        .c:1
  71. **        .d:2
  72. **
  73. ** Storage cost is 20 bytes for each segment (text between '.'), plus
  74. ** space of actual non-'.' text.
  75. **
  76. ** So, approximately 50 bytes average per attribute.  100 global
  77. ** attibutes, plus 500 application-specific attributes = 3Kbytes.
  78. ** This is very cheap.
  79. **
  80. ** main() loads the app_defs.sys file.  Access is then via:
  81. **
  82. **    char* get_default_text(char* attribute)
  83. **
  84. ** STATUS:
  85. **   For evaluation - TSR linkage not implemented.
  86. **   main() includes TEST code that allows interactive examination
  87. **   of the system.
  88. **
  89. **   Spaces on either side of the ":" in app_defs.sys file, are considered
  90. **   part of the attribute or value.
  91. */
  92.  
  93. #include <stdio.h>
  94. #include <string.h>
  95.  
  96. #define MAXPATTERN 128
  97. #define MAXVALUE 128
  98. #define WILDCARD '*'
  99. #define APPDEFS "app_defs.sys" /* ie. in root drive */
  100.  
  101. void test();
  102.  
  103. typedef struct NodeRec {
  104.     struct NodeRec* next;
  105.     char* match_segment;
  106.     char* value;
  107.     struct NodeRec* subnode;
  108.     int priority;
  109. } Node;
  110.  
  111. void dump(Node* node, int indent)
  112. /* Show tree as indented list (for debugging) */
  113. {
  114.     static char* space="                         ";
  115. #define maxspace 25
  116.  
  117.     if (node) {
  118.         if (node->value) {
  119.             printf("%s%s %s\n",
  120.                 space+maxspace-indent,
  121.                 node->match_segment,
  122.                 node->value
  123.             );
  124.         } else {
  125.             printf("%s%s\n",space+maxspace-indent,node->match_segment);
  126.         }
  127.  
  128.         dump(node->subnode,indent+1);
  129.         dump(node->next,indent);
  130.     }
  131. }
  132.  
  133. Node* new_node()
  134. {
  135.     return (Node*)malloc(sizeof(Node));
  136. }
  137.  
  138. char* submatch(char* a, char* b)
  139. /* Match a against b, up to '.' or '\0' in a.
  140. ** Return next segment (in a) after '.' or on '\0', or 0 if no match.
  141. */
  142. {
  143.     while (*a==*b && *b && *a && *a!='.') {
  144.         a++; b++;
  145.     }
  146.  
  147.     if (*b) return 0; /* No match */
  148.     if (*a==*b) return a; /* Match - at end */
  149.     if (*a=='.') return a+1; /* Match - at . */
  150.     return 0; /* How did this happen? */
  151. }
  152.  
  153. char* submatch_wild(char* a, char* b, int skip_dots)
  154. /* Match a against b, up to '.' or '\0' in a.
  155. ** Return next segment (in a) after '.' or on '\0', or 0 if no match.
  156. ** Honour wildcard '*' in b.  Allow wildcards to consume up to
  157. ** the given number of dots.
  158. **
  159. ** (the requirement of skip_dots increases the complexity of this function)
  160. */
  161. {
  162.     while (1) { /* This loop removes a simple tail recursion */
  163.  
  164.         if (*b==WILDCARD) {
  165.             char* try=0;
  166.             if (*a && *a!='.') try=submatch_wild(a+1,b,skip_dots);
  167.             if (try) return try;
  168.             if (*a=='.' && skip_dots) try=submatch_wild(a+1,b,skip_dots-1);
  169.             if (try) return try;
  170.             try=submatch_wild(a,b+1,skip_dots);
  171.             return try;
  172.         }
  173.  
  174.         if (*a=='.' || !*a) {
  175.             /* End of a */
  176.             if (*b) return 0;
  177.             else return *a ? a+1 : a;
  178.         } else {
  179.             if (*a!=*b) {
  180.                 /* Match failed */
  181.                 return 0;
  182.             } else {
  183.                 /* Match so-far */
  184.                 a++;b++; /* This could be coded as tail recursion */
  185.             }
  186.         }
  187.     }
  188. }
  189.  
  190. char* cut_segment(char** pattern)
  191. /* Move *pattern forward to begining of next segment (after '.'),
  192. ** return copy of segment moved over.
  193. */
  194. {
  195.     char* start=*pattern;
  196.     while (**pattern && **pattern!='.') {
  197.         (*pattern)++;
  198.     }
  199.     if (**pattern) {
  200.         **pattern=0;
  201.         (*pattern)++;
  202.     }
  203.     return strdup(start);
  204. }
  205.  
  206.  
  207. Node* root=0;
  208.  
  209. void add_mapping(Node** node, char* pattern, char* value, int priority)
  210. /* Add given pattern->value mapping, with the given priority,
  211. ** to the tree at the given node.
  212. */
  213. {
  214.     if (*node) {
  215.         char* end_pat=submatch(pattern,(*node)->match_segment);
  216.         if (end_pat) {
  217.             /* Matches here */
  218.             if (*end_pat) {
  219.                 /* Still more to match */
  220.                 add_mapping(&(*node)->subnode, end_pat, value, priority);
  221.             } else {
  222.                 /* End of pattern - store value here */
  223.                 if ((*node)->value) {
  224.                     /* XXX Overriding (could generate message */
  225.                     free((*node)->value);
  226.                 }
  227.                 (*node)->value=strdup(value);
  228.                 (*node)->priority=priority;
  229.             }
  230.         } else {
  231.             /* No match */
  232.             add_mapping(&(*node)->next, pattern, value, priority);
  233.         }
  234.     } else {
  235.         /* New node */
  236.  
  237.         *node=new_node();
  238.         (*node)->next=0;
  239.         (*node)->match_segment=cut_segment(&pattern);
  240.         (*node)->subnode=0;
  241.  
  242.         if (*pattern) {
  243.             /* More to go */
  244.             (*node)->value=0;
  245.             (*node)->priority=0;
  246.             add_mapping(&(*node)->subnode, pattern, value, priority);
  247.         } else {
  248.             /* Leaf node */
  249.             (*node)->value=strdup(value);
  250.             (*node)->priority=priority;
  251.         }
  252.     }
  253. }
  254.  
  255. int count_dots(char* str)
  256. {
  257.     int n;
  258.     for (n=0; *str; str++) {
  259.         if (*str=='.') n++;
  260.     }
  261.     return n;
  262. }
  263.  
  264. char* look_up(Node* node, char* pattern, int* priority)
  265. /* Lookup the given pattern, return the value with the highest
  266. ** priority in the given tree.  Set *priority.
  267. **
  268. ** (simplistic algorithm used for matching dots)
  269. */
  270. {
  271.     if (node) {
  272.         char* best_result=0;
  273.         int best_priority=-1;
  274.         char* local_result=0;
  275.         int local_priority=0;
  276.         int dots=count_dots(pattern);
  277.  
  278. #   define UPDATE_BEST \
  279.     if (local_result && local_priority>best_priority) {     \
  280.         best_priority=local_priority; \
  281.         best_result=local_result; \
  282.     }
  283.  
  284.         while (dots>=0) {
  285.             char* end_pat=submatch_wild(pattern,node->match_segment,dots);
  286.  
  287.             if (end_pat) {
  288.                 /* Matches here */
  289.                 if (*end_pat) {
  290.                     /* Still more to match */
  291.                     local_result=look_up(node->subnode, end_pat, &local_priority);
  292.                     UPDATE_BEST
  293.                 } else {
  294.                     /* End of pattern - retrieve value from here */
  295.                     /* (perhaps 0) */
  296.                     local_result=node->value;
  297.                     local_priority=node->priority;
  298.                     UPDATE_BEST
  299.                 }
  300.             }
  301.  
  302.             dots--;
  303.         }
  304.  
  305.         /* Try siblings */
  306.         local_result=look_up(node->next, pattern, &local_priority);
  307.         UPDATE_BEST
  308.  
  309. #   undef UPDATE_BEST
  310.  
  311.         *priority=best_priority;
  312.         return best_result;
  313.     } else {
  314.         return 0;
  315.     }
  316. }
  317.  
  318.  
  319. main()
  320. {
  321.     FILE* file=fopen(APPDEFS,"r");
  322.  
  323.     if (file) {
  324.         char pattern[MAXPATTERN];
  325.         char value[MAXVALUE];
  326.         int priority=1;
  327.  
  328.         while (1) {
  329.             char first=fgetc(file);
  330.             ungetc(first,file);
  331.  
  332.             if (first=='#') {
  333.                 /* comment */
  334.                 fscanf(file,"%*[^:\n]");
  335.             } else {
  336.                 if (fscanf(file,"%[^:\n]:%[^\n]\n",pattern,value)!=2)
  337.                     break; /* END */
  338.  
  339.                 add_mapping(&root,pattern,value,priority);
  340.                 priority++;
  341.             }
  342.         }
  343.  
  344.         fclose(file);
  345.     }
  346.  
  347.     /* Install look-up function */
  348.  
  349.     /* Terminate, stay resident */
  350.  
  351.     test();
  352. }
  353.  
  354.  
  355.  
  356.  
  357. /* The functions below would be exported via a cookie interface */
  358.  
  359. char* get_default_text(char* attribute)
  360. {
  361.     int priority;
  362.     return look_up(root,attribute,&priority);
  363. }
  364.  
  365. char* get_default_number(char* attribute, int* intvalue)
  366. {
  367.     char* value=g